/*
 * 9.5
 * Given a sorted array of strings which is interspersed with empty strings, write a meth-
 * od to find the location of a given string.
 * Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”] will return 4
 * Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1
 */
#include <stdio.h>
#include <string.h>

int search(const char **strs, int n, const char *s)
{
    int left = 0, right = n - 1;
    while (left <= right) {
        int middle = left + (right - left) / 2;
        if (strcmp(strs[middle], s) == 0) {
            return middle;
        }
        int m = middle;
        while (m >= 0 && strs[m] == "") {
           m--;
        }
        if (m == 0) {
            left = middle;
        } else {
            int cmp = strcmp(strs[m], s);
            if (cmp == 0) {
                return m;
            } else if (cmp < 0) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
    }
    return -1;
}

int main()
{
    const char *strs[] = { "at", "", "", "", "ball", "", "", "car", "", "", "dad", "", "" };
    const char *s = "ball";
    int i = search(strs, sizeof(strs)/sizeof(strs[0]), s);
    printf("find %s: %d\n", s, i);
    s = "ballcar";
    i = search(strs, sizeof(strs)/sizeof(strs[0]), s);
    printf("find %s: %d\n", s, i);
    return 0;
}
